package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

/**
 * 平衡二叉树
 *
 * @author yuhushuan
 * @date 2020/6/30 14:53
 */
public class _55_2_BalancedBinaryTree {
    private static boolean isBalanced(BinaryTreeNode root) {
        if (root == null) {
            return false;
        }
        return isBalancedCore(root, new int[]{0});
    }

    private static boolean isBalancedCore(BinaryTreeNode node, int[] depth) {
        if (node == null) {
            depth[0] = 0;
            return true;
        }
        int[] left = new int[1];
        int[] right = new int[1];
        if (isBalancedCore(node.left, left) && isBalancedCore(node.right, right)) {
            int diff = left[0] - right[0];
            if (diff >= -1 && diff <= 1) {
                depth[0] = 1 + Math.max(left[0], right[0]);
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        BinaryTreeNode root;

        // 功能测试
        // 完全二叉树
        root = BinaryTreeNode.createCompleteBinaryTree(19);
        print(root);

        // 不是平衡二叉树
        root = BinaryTreeNode.getTestBinaryTree_1();
        print(root);
        // 只有左子树
        root = BinaryTreeNode.createOnlyLeftNodeTree(5);
        print(root);
        // 只有右子树
        root = BinaryTreeNode.createOnlyRightNodeTree(3);
        print(root);

        // 特殊输入测试
        print(new BinaryTreeNode(3));
        print(null);
    }

    private static void print(BinaryTreeNode root) {
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        System.out.println("是平衡二叉树：" + isBalanced(root));
        System.out.println();
    }
}
